The fast Fourier Transform and fast Wavelet Transform for Patterns on the Torus

摘要

We introduce a fast Fourier transform on regular d-dimensional lattices. Weinvestigate properties of congruence class representants, i.e. their ordering,to classify directions and derive a Cooley-Tukey-Algorithm. Despite the fastFourier techniques itself, there is also the advantage of this transform to beparallelized efficiently, yielding faster versions than the one-dimensionalFourier transform. These properties of the lattice can further be used toperform a fast multivariate wavelet decomposition, where the wavelets are givenas trigonometric polynomials. Furthermore the preferred directions of thedecomposition itself can be characterised.